The present invention relates to techniques for performing distribution of objects or processing tasks using consistent hashing techniques with an initial distribution of processing.
One issue relating to distributed processing is distributing objects or processing tasks (keys) among the resources (buckets) that are available to store and/or process the objects and tasks. Conventional systems may distribute keys using a conventional hash function, such as generating a hash of an object or task, then finding the modulus to the base of the number of buckets, and distributing accordingly. In this situation, if a bucket is added or removed, all or almost all keys must be redistributed.
The use of a special hash function, known as a consistent hash function, may greatly reduce the keys that must be redistributed when the number of buckets changes. For example, an existing consistent hash function may map keys to a set of buckets. Similar to a conventional hash function, the key set (for example, web requests) may be very large and not evenly distributed, while the bucket set (for example, a population of web servers) may be finite. The hash function may deterministically distribute the keys among the buckets in an even manner. Unlike conventional hashing, existing consistent hashing minimizes the mapping changes (called “reshuffling”) when the set of buckets changes (for example, when web servers are added or removed). Existing consistent hashing has many applications and is fundamental to web caching, storage, in-memory caches, distributed hash tables, etc.
There are a number of conventional hash functions and implementations, such as the existing consistent hash function, the existing rendezvous consistent hash function, the existing jump consistent hash function, the existing GOOGLE® Maglev hash function, and the existing permutation-based hash function. Each of these functions and implementation has advantages and disadvantages. However, typical disadvantages may include high memory use and complexity, high computational complexity, and relatively high numbers of keys that must be reshuffled.
A need arises for techniques that implement a consistent hash function that provides reduced memory use and complexity, reduced computational complexity, and relatively low numbers of keys that must be reshuffled compared to current techniques.